package 动态规划.经典动态规划题目.背包问题;

public class 分割等和子集_416 {
    public static void main(String[] args) {
        System.out.println(new 分割等和子集_416().canPartition(new int[]{1, 2, 3, 5}));
    }


    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        //和是奇数，不可能平分成两个和相等的子集
        if (sum % 2 != 0) {
            return false;
        }

        int n = nums.length;
        //构建背包
        sum = sum / 2;
        //dp[i][j]=x；对于前i个物品。背包容量为j时候，若x=true，则恰好可以把背包装满，x=false，则不能把背包装满
        boolean[][] dp = new boolean[n + 1][sum + 1];//多的一个大小，是留给base case的

        /*
        base case:
            dp[0][..]=false：没有物品可以装，当然无法填满背包，在初始化数组的时候就完成了
            dp[..][0]=true：当背包容量为0，相当于已经装满了。即已经达到了sum
        */
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                /*j-nums[i-1]：背包剩余重量。要注意第i个物品的重量是nums[i-1]，因为i是从1开始的(因为i=0,j=0留给了base case)，而数组的索引是从0开始的。
                 */
                if (j - nums[i - 1] < 0) {
                    // 背包满了无法装入
                    dp[i][j] = dp[i - 1][j];
                } else {
                    //选择装入或者不装入，只要有一个为true，证明存在一种方案恰好装满背包
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[n][sum];
    }
}
